﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.DataStructures.Maps;
using Algoritmia.DataStructures.Queues;
using Algoritmia.Utils;
using Sets = Algoritmia.DataStructures.Sets;

namespace Algoritmia.Problems.ConnectedComponents
{
    public class StrongConnectedComponentsFinder<T> : IStrongConnectedComponentsFinder<T>
    {
        private readonly Func<IEnumerable<T>, Sets.ISet<T>> _createSet;
        private readonly Func<IEnumerable<T>, ILifo<T>> _createLifo;
        private readonly Func<IEnumerable<T>, IMap<T, int>> _createMap;
        private readonly EqualityComparison<T> _equalityComparison;

        public StrongConnectedComponentsFinder(Func<IEnumerable<T>,Sets.ISet<T>> createSet = null,
            Func<IEnumerable<T>,ILifo<T>> createLifo = null, Func<IEnumerable<T>,IMap<T,int>> createMap = null)
        {
            _createSet = createSet ?? (it => AlgoritmiaFactory.Sets<T>.Default);
            _createLifo = createLifo ?? (it => AlgoritmiaFactory.Lifos<T>.Default);
            _createMap = createMap ?? (it => AlgoritmiaFactory.Maps<T, int>.Default);
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison<T>();
        }

        #region IStrongConnectedComponentsFinder<T> Members

        public IEnumerable<IEnumerable<T>> StrongConnectedComponents(IDigraph<T> g)
        {
            var stack = _createLifo(g.V);
            var l = _createMap(g.V);
            var d = _createMap(g.V);
            var visited = _createSet(g.V);
            var dead = _createSet(g.V);
            var components = new List<List<T>>();

            Action<T> recursiveStrongComponents = null;

            recursiveStrongComponents = u =>
                                            {
                                                visited.Add(u);
                                                stack.Push(u);
                                                d[u] = d.Count;
                                                l[u] = d[u];

                                                foreach (var s in g.Successors(u))
                                                {
                                                    if (!dead.Contains(s))
                                                    {
                                                        if (!visited.Contains(s))
                                                        {
                                                            recursiveStrongComponents(s);
                                                            l[u] = Math.Min(l[u], l[s]);
                                                        }
                                                        else
                                                        {
                                                            l[u] = Math.Min(l[u], d[s]);
                                                        }
                                                    }
                                                }
                                                if (l[u] == d[u])
                                                {
                                                    var comp = new List<T>();
                                                    T v;
                                                    do
                                                    {
                                                        v = stack.Pop();
                                                        comp.Add(v);
                                                        dead.Add(v);
                                                    } while (!_equalityComparison(v, u));
                                                    components.Add(comp);
                                                }
                                            };
                                                     

            recursiveStrongComponents(g.V.First());
            return components;
        }

        #endregion
    }
}
